package com.fps.webshop.question.question0300_0399;

import java.util.HashMap;
import java.util.Map;

/**
 * 387. 字符串中的第一个唯一字符
 * 
 * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
 * 
 * 示例：
 * s = "leetcode"
 * 返回 0
 * 
 * s = "loveleetcode"
 * 返回 2
 * 
 * 提示：你可以假定该字符串只包含小写字母。
 */
public class Question387 {
	
	/**
	 * 第一次提交，使用Map记录每个元素的位置和是否重复，但比较耗时
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		19 ms	38.8 MB	Java	2021/08/16 13:47
	 * 
	 * 执行用时：19 ms, 在所有 Java 提交中击败了68.92%的用户
	 * 内存消耗：38.8 MB, 在所有 Java 提交中击败了68.99%的用户
	 */
	public static int firstUniqChar1(String s) {
		char[] ss = s.toCharArray();
		Map<Character,Integer> ths = new HashMap<>();
		int min = ss.length+1;
		for(int i = ss.length-1;i>=0;i--) {
			if(ths.get(ss[i])==null) {
				ths.put(ss[i],i);
			}else {
				ths.put(ss[i],-1);
			}
		}
		for(Map.Entry<Character, Integer> a: ths.entrySet()) {
			if(a.getValue()!=-1&&a.getValue()<min) {
				min = a.getValue();
			}
		}
		if(min==ss.length+1) {
			min = -1;
		}
		return min;
    }
	
	/**
	 * 第二次提交，使用Map记录每个元素出现的次数，然后再次遍历根据Map去取值判断
	 * 更为耗时，不好
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		29 ms	39 MB	Java	2021/08/16 13:54
	 * 
	 * 执行用时：29 ms, 在所有 Java 提交中击败了45.16%的用户
	 * 内存消耗：39 MB, 在所有 Java 提交中击败了45.69%的用户
	 */
	public static int firstUniqChar2(String s) {
		char[] ss = s.toCharArray();
		Map<Character,Integer> ths = new HashMap<>();
		for(int i = ss.length-1;i>=0;i--) {
			if(ths.get(ss[i])==null) {
				ths.put(ss[i],1);
			}else {
				ths.put(ss[i],ths.get(ss[i])+1);
			}
		}
		for(int i = 0;i<ss.length;i++) {
			if(ths.get(ss[i])==1) {
				return i;
			}
		}
		return -1;
    }
	
	
	public static void main(String[] args) {
		System.out.print(firstUniqChar1("loveleetcode"));
	}
}
